Round-robin (“RR”) is a work-scheduling technique that has been used in many types of computer systems. Standard RR scans work queues, on which pending work is stored, repetitively and in a fixed order. Each queue is allocated a fixed amount of time. When a queue with pending work is found, some or all of these pending requests are processed within the fixed amount of time. The request is a data packet in communication networks. In a typical implementation of RR, the RR scheduler scans work queues on which pending work is stored, repetitively and in a fixed order, and when a queue with pending work is found, a single request is processed. However, the request service may vary in duration. Standard RR is computationally very efficient, but it lacks controllability and is prone in both cases to undesirable “burstiness”, and “unfairness”. Generally, scheduling “fairness” is understood to mean providing service to queues in a fair manner, such as by providing each queue equal service on average. Other implementation of RR, referred to as Weighted Round Robin (WRR), attempt to allocate each queue a number of requests that are eligible for service in a round. In this case, the RR scheduler scans work queues on which pending work is stored, repetitively and in a fixed order, and when a queue with pending work is found, up to the assigned number of requests eligible for service in a round are processed from that queue. WRR still faces the same issues of burstiness and unfairness (in the presence of service requests that take variable time) as RR.
Thus standard WRR has been modified in various ways to overcome such drawbacks. See, e.g., Shreedhar et al., 1996, IEEE/ACM Trans. on Networking 4(3), pp. 375-385. An example of a variant WRR scheduling technique now believed to be used in communication switches with variable packet sizes repetitively performs the steps of assigning each queue a service weight and then servicing each queue with backlogged data until the assigned service weight is exhausted. However the service weight is measured, entire packets must be transmitted in their entirety in order to avoid packet corruption due to the interleaving of different packets on output links. Although this variant RR technique does grant all work queues on average their assigned service even if one or more of the queues are continuously backlogged, it can often cause undesirable short-term variance in packet throughput (jitter) as well as burstiness.
Similarly, other known variant RR techniques that improve one aspect of scheduling service often do so at the cost of unintended consequences for other aspects of scheduling service. Accordingly, what is needed in the scheduling arts are schedulers controllable to achieve determined service goals (also referred to as quality-of-service (QOS) goals) while retaining the computational efficiency. Computational efficiency is particularly key in modern communication switches and routers that need to service packet queues on modern high-throughput communication links (often at speeds excess of 100, or 200, or 500, or more megabits/sec).
Citation or identification of any reference in this section or any section of this application shall not be construed that such reference is available as prior art to the present invention.